#pragma once
#include<iostream>
using namespace std;

template<class T>
struct BTNode
{
	T _data;
	BTNode<T>* left;
	BTNode<T>* right;

	BTNode(const T& key)
		:_data(key)
		,left(nullptr)
		,right(nullptr)
	{}
};

template<class T>
class BSTree
{
public:
	typedef BTNode<T> Node;

	bool Insert(const T& key)
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
		}
		else
		{
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_data < key)
				{
					parent = cur;
					cur = cur->right;
				}
				else if (cur->_data > key)
				{
					parent = cur;
					cur=cur->left;
				}
				else
				{
					return false;
				}
			}
			if (parent->_data > key)
			{
				parent->left = new Node(key);
			}
			else
			{
				parent->right = new Node(key);
			}
		}
		return true;
	}

	void Inorder()
	{
		_Inorder(_root);
	}

	bool _Erase(const T& key)
	{
		/*if (_root == nullptr)
		{
			return false;
		}*/

		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (cur->_data < key)
			{
				parent = cur;
				cur = cur->right;
			}
			else if (cur->_data > key)
			{
				parent = cur;
				cur = cur->left;
			}
			else
			{
				if (cur->left == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->right;
					}
					else
					{
						if (cur == parent->left)
						{
							parent->left = cur->right;
						}
						else
						{
							parent->right = cur->right;
						}
					}
					delete cur;
				}
				else if (cur->right == nullptr)
				{
					if (cur == _root)
					{
						_root = cur->left;
					}
					else
					{
						if (cur == parent->left)
						{
							parent->left = cur->left;
						}
						else
						{
							parent->right = cur->left;
						}
					}
					delete cur;
				}
				else
				{
					Node* parent = cur;
					Node* subnode = cur->right;
					while (subnode->left)
					{
						parent = subnode;
						subnode = subnode->left;
					}
					swap(cur->_data, subnode->_data);
					if (subnode == parent->left)
					{
						parent->left = subnode->right;
					}
					else if (subnode == parent->right)
					{
						parent->right = subnode->right;
					}
					delete subnode;
				}
				return true;
			}

		}
		return false;
	}

	bool Find(const T& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_data > key)
			{
				cur = cur->left;
			}
			else if (cur->_data < key)
			{
				cur = cur->right;
			}
			else
			{
				return true;
			}
		}
		return false;
	}

	bool InsertR(const T& key)
	{
		return _InsertR(_root, key);
	}

	bool FindR(const T& key)
	{
		return _FindR(_root, key);
	}

	bool EraseR(const T& key)
	{
		return _EraseR(_root, key);
	}


	~BSTree()
	{
		Destory(_root);
	}

	BSTree()
	{}


	BSTree( const BSTree<T>& t)
	{
		_root = copy(t._root);
	}

	BSTree<T>& operator=(BSTree<T> t)
	{
		swap(_root, t._root);
		return *this;
	}

private:

	Node* copy(Node* root)
	{
		if (root == nullptr)
		{
			return nullptr;
		}
		Node* newRoot = new Node(root->_data);
		newRoot->left = copy(root->left);
		newRoot->right = copy(root->right);
		return newRoot;
	}

	Node* _root = nullptr;

	void _Inorder(Node* _root)
	{
		if (_root == nullptr)
			return;
		_Inorder(_root->left);
		cout << _root->_data<<"  ";
		_Inorder(_root->right);
	}

	bool _InsertR(Node* & root, const T& key)
	{
		if (root == nullptr)
		{
			root = new Node(key);
		}

		if (root->_data > key)
		{
			return _InsertR(root->left, key);
		}
		else if(root->_data<key)
		{
			return _InsertR(root->right, key);
		}
		else
		{
			return false;
		}
	}

	bool _FindR(Node* root, const T& key)
	{
		if (root == nullptr)
		{
			return false;
		}
		if (root->_data > key)
		{
			return _FindR(root->left, key);
		}
		else if (root->_data < key)
		{
			return _FindR(root->right, key);
		}
		else
		{
			return true;
		}
	}

	bool _EraseR(Node*& root, const T& key)
	{
		if (root == nullptr)
		{
			return false;
		}
		if (root->_data > key);
		{
			return _EraseR(root->left, key);
		}
		if ((root->_data < key))
		{
			return _EraseR(root->right, key);
		}
		else
		{
			if (root->left == nullptr)
			{
				Node* temp = root;
				root = root->right;
				delete temp;
			}
			else if (root->right==nullptr)
			{
				Node* temp = root;
				root = root->right;
				delete temp;
			}
			else
			{
				Node* subnode = root->right;
				while (subnode->left)
				{
					subnode = subnode->left;
				}
				swap(root->_data, subnode->_data);
				_EraseR(root->right, key);

			}
		}
	}

	void Destory(Node*& root)
	{
		if (root == nullptr)
			return;
		Destory(root->left);
		Destory(root->right);
		delete root;
		root = nullptr;
	}




};



